# 普通方法实现递归


def recursion(num):
    if num <= 1:
        return num
    else:
        print('重复调用')
        return recursion(num - 1) + recursion(num - 2)


for x in range(10):
    print(recursion(x))

"""
0
1
重复调用
1
重复调用
重复调用
2
重复调用
重复调用
重复调用
重复调用
3
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
5
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
8
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
13
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
21
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
重复调用
34
"""


# 普通方法为斐波那契函数添加缓存

# dict_data = {2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34}
#
#
# def recursion(num):
#     if num <= 1:
#         return num
#     else:
#         return dict_data[num]
#
#
# for x in range(10):
#     print(recursion(x))


# 上面方法的另一种写法
# dict_data = {}
#
#
# def recursion(num):
#     if num <= 1:
#         return num
#     else:
#         if num in dict_data:
#             return dict_data[num]
#         else:
#             return recursion(num-1) + recursion(num-2)
#
#
# for x in range(10):
#     print(recursion(x))


# 使用装饰器实现为斐波那契函数添加缓存


def decorator(func):
    cache = {}

    def warp(*args, **kwargs):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]

    return warp


@decorator
def recursion(num):
    if num <= 1:
        return num
    else:
        result = recursion(num - 1) + recursion(num - 2)
        return result


for x in range(10):
    print(recursion(x))

# 迭代器：是可以进行索引，for循环，next()方法的对象

# 生成器：通过yield生成迭代器
